package com.zjj.algorithm.learning.leetcode.array;

/**
 * 42. 接雨水 困难
 * <p>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 示例 2：
 * <p>
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *
 * @author zjj_admin
 * @date 2022/11/11 14:26
 */
public class TrappingRainWater {

    public static void main(String[] args) {
        int[] height = new int[]{4, 2, 0, 3, 2, 5};
        int res = trap(height);
        System.out.println("res = " + res);

    }


    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 42.2 MB
     * 击败
     * 46.79%
     *
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        //给定两个指针
        int left = 0;
        int right = height.length - 1;
        //左边的最大值，和右侧的最大值
        int maxLeft = 0;
        int maxRight = 0;
        int res = 0;
        while (left < right) {
            maxLeft = Math.max(maxLeft, height[left]);
            maxRight = Math.max(maxRight, height[right]);
            if (maxLeft < maxRight) {
                res += maxLeft - height[left];
                left++;
            } else {
                res += maxRight - height[right];
                right--;
            }
        }
        return res;
    }
}
